package com.practice.zuocy.base.class12;

/**
 * 【leetcode 1143 最长公共子序列】（TODO：一个作行一个左列的对应模型）
 * 【题目】：
 * 给定两个字符串text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 * 【示例1】：
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 * 【示例2】：
 * 输入：text1 = "abc", text2 = "abc"
 * 输出：3
 * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
 * 【示例3】：
 * 输入：text1 = "abc", text2 = "def"
 * 输出：0
 * 解释：两个字符串没有公共子序列，返回 0 。
 * 【提示】：
 * 1 <= text1.length, text2.length <= 1000
 * text1 和 text2 仅由小写英文字符组成。
 *
 * @author lineng
 * @create 2021-05-01 17:25
 */
// 这个问题leetcode上可以直接测
// 链接：https://leetcode.com/problems/longest-common-subsequence/
public class Code04_LongestCommonSubsequence {

	// https://leetcode-cn.com/problems/longest-common-subsequence/
	// AC 通过
	public static int longestCommonSubsequence(String text1, String text2) {
		if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
			return 0;
		}
		return myDp(text1.toCharArray(), text2.toCharArray());
	}

	// chs1[0...i-1]和chs2[0...j-1]已经做了决定
	// 轮到chs1[i]和chs2[j]做决定
	// dp[i][j]表示
	// chs1[0...i]与chs2[0...j]的最长公共子序列的长度
	// int[][] dp = new int[chs1.length][chs2.length]，最终返回dp[chs1.length-1][chs2.length-1]
	// 求dp[i][j]时：
	// 如果 chs1[i]!=chs2[j] ====> dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]
	// 如果 chs1[i]==chs2[j] ===> dp[i][j] = dp[i-1][j-1] + 1
	public static int myDp(char[] chs1, char[] chs2) {
		int N = chs1.length;
		int M = chs2.length;
		int[][] dp = new int[N][M];
		// 填好第0行，第0行中一旦发现chs2[i]==chs1[0], 当前位置和后面位置都为1
		int cloIndex = -1;
		for (int i = 0; i < M; i++) {
			if (chs1[0] == chs2[i]) {
				cloIndex = i;
				break;
			}
		}
		if (cloIndex >= 0) {
			for (int i = cloIndex; i < M; i++) {
				dp[0][i] = 1;
			}
		}
		// 填好第0列，第0列中一旦发现chs1[i]==chs2[0], 当前位置和下面位置都为1
		int rowIndex = -1;
		for (int i = 0; i < N; i++) {
			if (chs2[0] == chs1[i]) {
				rowIndex = i;
			}
		}
		if (rowIndex >= 0) {
			for (int i = rowIndex; i < N; i++) {
				dp[i][0] = 1;
			}
		}
		// 填好普遍位置dp[i][j]
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < M; j++) {
				// 枚举公共子序列是否以chs1[i]或者chs2[j]结尾
				// 可以有如下几种选择（每种都可以选，只是最后一种有条件）：
				// (1) 子序列既不以chs1[i]结尾也不以chs2[j]结尾 dp[i][j] = dp[i-1][j-1]
				// (2) 子序列以chs1[i]结尾，但是不以chs2[j]结尾 dp[i][j] = dp[i][j-1];
				// (3) 子序列不以chs1[i]结尾，但是以chs2[j]结尾 dp[i][j] = dp[i-1][j];
				// (4) 当chs1[i] == chs2[j]时，子序列可以即以chs1[i]结尾也以chs2[j]结尾，dp[i][j] = dp[i-1][j-1]+1

				dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]);
				if (chs1[i] == chs2[j]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
			}
		}
		return dp[N - 1][M - 1];
	}









	public static int longestCommonSubsequence1(String s1, String s2) {
		if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
			return 0;
		}
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		// 尝试
		return process1(str1, str2, str1.length - 1, str2.length - 1);
	}

	public static int process1(char[] str1, char[] str2, int i, int j) {
		if (i == 0 && j == 0) {
			return str1[i] == str2[j] ? 1 : 0;
		} else if (i == 0) {
			if (str1[i] == str2[j]) {
				return 1;
			} else {
				return process1(str1, str2, i, j - 1);
			}
		} else if (j == 0) {
			if (str1[i] == str2[j]) {
				return 1;
			} else {
				return process1(str1, str2, i - 1, j);
			}
		} else { // i != 0 && j != 0
			int p1 = process1(str1, str2, i - 1, j);
			int p2 = process1(str1, str2, i, j - 1);
			int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
			return Math.max(p1, Math.max(p2, p3));
		}
	}

	public static int longestCommonSubsequence2(String s1, String s2) {
		if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
			return 0;
		}
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		int N = str1.length;
		int M = str2.length;
		int[][] dp = new int[N][M];
		dp[0][0] = str1[0] == str2[0] ? 1 : 0;
		for (int j = 1; j < M; j++) {
			dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
		}
		for (int i = 1; i < N; i++) {
			dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
		}
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < M; j++) {
				int p1 = dp[i - 1][j];
				int p2 = dp[i][j - 1];
				int p3 = str1[i] == str2[j] ? (1 + dp[i - 1][j - 1]) : 0;
				dp[i][j] = Math.max(p1, Math.max(p2, p3));
			}
		}
		return dp[N - 1][M - 1];
	}

}
